package day005;

import java.util.Comparator;
import java.util.PriorityQueue;


/**
 * 贪心算法
 * 输入正数数组costs,profits
 * 正数 k,m
 * costs[i] 表示i号项目的花费
 * profits[i] 表示i号项目表示再扣除花费之后还能挣到的钱
 * k 表示你只能穿行的最多做的项目
 * m 表示你的资金
 */
public class Code02_IPO {

    public static class Node {
        public int profit;
        public int capital;

        public Node(int profit, int costs) {
            this.profit = profit;
            this.capital = costs;
        }
    }

    // 花费 升序
    public static class MinCostComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.capital - o2.capital;
        }
    }

    // 利润 降序
    public static class MaxProfitComparator implements  Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o2.profit - o1.profit;
        }
    }

    /**
     *
     * @param k 最多投几个项目
     * @param w 初始资金
     * @param profits 项目获得的利润
     * @param costs 项目需要投入的资金
     * @return
     */
    public static int findMaxCapital(int k, int w, int[] profits, int[] costs){
        // 花费最小堆，利润最大堆
        PriorityQueue<Node> minCost = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Node> maxProfit = new PriorityQueue<>(new MaxProfitComparator());
        for(int i = 0; i < profits.length; i++){
            minCost.add(new Node(profits[i], costs[i]));
        }
        for (int i = 0; i < k; i++){
            while(!minCost.isEmpty() && minCost.peek().capital <= w){
                maxProfit.add(minCost.poll());
            }
            if(maxProfit.isEmpty()){
                return w;
            }
            w += maxProfit.poll().profit;
        }
        return w;
    }


}
